package queue

import (
	"sync/atomic"
	"unsafe"
)

type LKFQueue struct {
	head, tail unsafe.Pointer
}
type node struct {
	value interface{}
	next  unsafe.Pointer
}

func NewLKFQueue() *LKFQueue {
	n := unsafe.Pointer(&node{})
	return &LKFQueue{
		head: n,
		tail: n,
	}
}

// Enqueue 入队
func (q *LKFQueue) Enqueue(v interface{}) {
	n := &node{value: v}
	for {
		tail := (*node)(atomic.LoadPointer(&q.head))
		next := (*node)(atomic.LoadPointer(&tail.next))
		if tail == (*node)(atomic.LoadPointer(&q.head)) {
			if next == nil {
				if cas(&tail.next, next, n) {
					cas(&q.tail, tail, n) // 切换指针
					return
				}
			} else {
				cas(&q.tail, tail, next)
			}
		}
	}
}

func (q *LKFQueue) Dequeue() interface{} {
	for {
		head := (*node)(atomic.LoadPointer(&q.head))
		tail := (*node)(atomic.LoadPointer(&q.tail))
		next := (*node)(atomic.LoadPointer(&head.next))
		if head == (*node)(atomic.LoadPointer(&q.head)) {
			if head == tail { // 头尾相同表示无元素
				if next == nil { //再次检查是否有无元素
					return nil
				}
				cas(&q.tail, tail, next)
			} else {
				// 出队
				v := next.value
				if cas(&q.head, head, next) {
					return v
				}
			}
		}
	}
}

func cas(q *unsafe.Pointer, old, new *node) bool {
	return atomic.CompareAndSwapPointer(q, unsafe.Pointer(old), unsafe.Pointer(new))
}
